package 常用类库API;
/*
 二叉树数据结构，实现方法同链表需要内部类和递归
 二叉树的数据结构 :
   根节点，比根节点大的放右边，比根节点小的放左边，依次往下分叉(相等的放哪里都可以比如<=的放左边)
   比如 8,4,10,6,9,11,7  二叉树分布如下
      8
	 / \
	4   10
   / \  / \
     6  9  11
	/ \
	   7
*/
public class 二叉树数据结构
{
	public static void main(String[] args){
		BinaryTree bt=new BinaryTree();
		bt.add(8);
		bt.add(4);
		bt.add(10);
		bt.add(6);
		bt.add(9);
		bt.add(11);
		bt.add(7);
		bt.print();
	}
}

class BinaryTree{
	private Node root;
	
	public void add(int data){
		if(root==null){
			root=new Node(data);
		}else{
			root.addNode(data);
		}
	}
	public void print(){
		root.printNode();
	}
	
	private class Node{
		private int data;
		private Node left;
		private Node right;
		
		public Node(int data){
			this.data=data;
		}
		//添加节点
		public void addNode(int data){
			if(this.data>=data){
				if(this.left==null){
					this.left=new Node(data);
				}else{
					this.left.addNode(data);
				}
			}else{
				if(this.right==null){
					this.right=new Node(data);
				}else{
					this.right.addNode(data);
				}
			}
		}
		//输出节点，常用 中序法(左>中>右)
		//比如 上面的例子，8先(左4，4没有左边，输出4，判断4的右边6没有左边，输出6，有右边7，判断7无左输出7无右.)输出中间8....
		public void printNode(){
			//先输出左边
			if(this.left!=null){
				this.left.printNode();
			}
			//左边输出完，输出中间
			System.out.print(this.data+"->");
			//最后输出右边
			if(this.right!=null){
				this.right.printNode();
			}
		}
	}
}
